package dp;

import java.util.Scanner;

//最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别： 
//子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。
public class LongestCommonSubsequence {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextLine()) {
			String string = scanner.nextLine();
			String[] strings = string.split(" ");
			for (String string2 : strings) {
				System.out.println("**" + string2);
			}
//			System.out.println(strings[0] + "*isjjj*"  + strings[strings.length - 1]);
			System.out.println(getLongest(strings[0], strings[strings.length - 1]));
		}
		scanner.close();
	}
	
	//dp[i][j] 表示 序列长度分别为i和j的两个序列中的最长公共子序列
	//dp[i][j]  = dp[i - 1][j - 1] + 1  ( if S[i] == T[j])
	//dp[i][j]  = dp[i - 1][j ]   ( if S[i] != T[j])
	//边界条件：dp[0][j] = 0, dp[i][0] = 0
	public static int longest(String S, String T){
		if (S == null || T == null) {
			return -1;
		}
		if(S.length() <= 0  || T.length() <= 0 ){
			return 0;
		}
		int[][] result = new int[S.length() + 1][T.length() + 1];
		for (int i = 1; i < result.length; i++) {
			for (int j = 1; j < result[0].length; j++) {
				if(S.charAt(i - 1) == T.charAt(j - 1)){
					result[i][j] = result[i- 1][j - 1] + 1;
				}else {
					result[i][j] = Math.max(result[i- 1][j], result[i][j - 1]);
				}
			}
		}
		for (int[] a: result) {
			for (int i : a) {
				System.out.print(i+"  ");
			}
			System.out.println();
		}
		return result[S.length()][T.length()];
	}
	
	//最长公共连续子串
	//dp[i][j]表示以i结尾的子串和以j结尾的子串最大的公共长度，如果charAt(i) != charAt(j),则为0
	//dp[i][j]  = dp[i - 1][j - 1] + 1  ( if S[i] == T[j])
	//dp[i][j]  = 0
	//最后维护一个变量记录最大值
	public static int getLongest(String S, String T){
		if (S == null || T == null) {
			return -1;
		}
		if(S.length() <= 0  || T.length() <= 0 ){
			return 0;
		}
		int max = -1;
		int[][] result = new int[S.length() + 1][T.length() + 1];
		for (int i = 1; i < result.length; i++) {
			for (int j = 1; j < result[0].length; j++) {
				if(S.charAt(i - 1) == T.charAt(j - 1)){
					result[i][j] = result[i- 1][j - 1] + 1;
				}else {
					result[i][j] = 0;
				}
				if(result[i][j] > max){
					max = result[i][j];
				}
			}
		}
		for (int[] a: result) {
			for (int i : a) {
				System.out.print(i+"  ");
			}
			System.out.println();
		}
		return max;
	}
}
